package ArraySort;

import java.util.Comparator;

public class MergeSort {
    public static void mergeSort(Comparable[] a) {//实现了Comparable接口的数组
        if (a.length >= 2) {
            int halfLength = a.length / 2; //求一半的数组长度
            Comparable[] firstHalf = new Comparable[halfLength];//前一半数组
            Comparable[] lastHalf = new Comparable[a.length - halfLength];//后一半数组
            divide(a, firstHalf, lastHalf); //将数组a中元素复制进两个数组 firstHalf和lastHalf
            mergeSort(firstHalf);//对前一半数组进行排序
            mergeSort(lastHalf);//对后一半数组进行排序
            merge(a, firstHalf, lastHalf);//将前一半数组和后一半数组进行组合
            //否则不执行任何操作
        }
    }

    public static void mergeSort(Comparable[] a, Comparator<Comparable> b) {//可传入comparator接口的数组
        if (a.length >= 2) {
            int halfLength = a.length / 2;
            Comparable[] firstHalf = new Comparable[halfLength];
            Comparable[] lastHalf = new Comparable[a.length - halfLength];
            divide(a, firstHalf, lastHalf);
            mergeSort(firstHalf, b);
            mergeSort(lastHalf, b);
            merge(a, firstHalf, lastHalf, b);
        }
    }

    public static void divide(Comparable[] a, Comparable[] firstHalf, Comparable[] lastHalf) {
        for (int i = 0; i < firstHalf.length; i++) {
            firstHalf[i] = a[i];
        }
        for (int i = 0; i < lastHalf.length; i++) {
            lastHalf[i] = a[firstHalf.length + i];
        }
    }


    public static void merge(Comparable[] a, Comparable[] firstHalf, Comparable[] lastHalf) {
        int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
        while ((firstHalfIndex < firstHalf.length) && (lastHalfIndex < lastHalf.length))//如果数组当前位置小于数组长度
        {
            if (firstHalf[firstHalfIndex].compareTo(lastHalf[lastHalfIndex]) < 0)//比较两个数组开始时的指针大小
            {
                a[aIndex] = firstHalf[firstHalfIndex];
                firstHalfIndex++;
            } else {
                a[aIndex] = lastHalf[lastHalfIndex];
                lastHalfIndex++;
            }
            //将比较小的数放入a数组然后较小数数组指针+1
            aIndex++;
            //a数组指针后移
        }
        while (firstHalfIndex < firstHalf.length) {
            a[aIndex] = firstHalf[firstHalfIndex];
            aIndex++;
            firstHalfIndex++;
        }
        //如果lastHalf数组还有剩余元素，将其复制到a中
        while (lastHalfIndex < lastHalf.length) {
            a[aIndex] = lastHalf[lastHalfIndex];
            aIndex++;
            lastHalfIndex++;
        }
    }
    //至少firstHalf和lastHalf数组之一已经完全复制到a中
    //如果firstHalf数组还有剩余元素，将其复制到a中


    public static void merge(Comparable[] a, Comparable[] firstHalf, Comparable[] lastHalf, Comparator<Comparable> b) {
        int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
        while ((firstHalfIndex < firstHalf.length) && (lastHalfIndex < lastHalf.length)) {
            if (b.compare(firstHalf[firstHalfIndex], lastHalf[lastHalfIndex]) < 0) {
                a[aIndex] = firstHalf[firstHalfIndex];
                firstHalfIndex++;
            } else {
                a[aIndex] = lastHalf[lastHalfIndex];
                lastHalfIndex++;
            }
            aIndex++;
        }
        while (firstHalfIndex < firstHalf.length) {
            a[aIndex] = firstHalf[firstHalfIndex];
            aIndex++;
            firstHalfIndex++;
        }
        while (lastHalfIndex < lastHalf.length) {
            a[aIndex] = lastHalf[lastHalfIndex];
            aIndex++;
            lastHalfIndex++;
        }
    }


}
